package com.ljy.my_study.leetcode.二叉树的层次遍历;

import java.util.ArrayList;
import java.util.List;

/**
 * @author James
 * @date 2018年9月27日
 */
public class TestMain {

	public static void main(String[] args) {
		TreeNode root=deserialize("3,9,20,null,null,15,7");
		System.out.println(levelOrder(root));
	}
	
	public static List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> listList=new ArrayList<>();
		if(root==null) {
			listList.add(new ArrayList<>());
			return new ArrayList<>();
		}
		List<Integer> rootList=new ArrayList<>(); 
		rootList.add(root.val);
		listList.add(rootList);
		List<TreeNode> nodeList=new ArrayList<>();
		nodeList.add(root);
		doLevelOrder(listList,nodeList);
        return listList;
    }
	
	private static void doLevelOrder(List<List<Integer>> listList,List<TreeNode> nodes) {
		if(nodes.size()>0) {
			List<TreeNode> sonNodes=new ArrayList<>();
			List<Integer> list=new ArrayList<>();
			for(TreeNode t:nodes) {
				if(t!=null) {
					if(t.left!=null) {
						list.add(t.left.val);
						sonNodes.add(t.left);
					}
					if(t.right!=null) {
						list.add(t.right.val);
						sonNodes.add(t.right);
					}
				}
			}
			if(!list.isEmpty())listList.add(list);
			doLevelOrder(listList,sonNodes);
		}
	}
	
	public static TreeNode deserialize(String data) {
		if(data==null||data.isEmpty()) {
			return null;
		}
		String[] arrStr=data.split(",");
		TreeNode root=null;
		TreeNode[] treeNodeArr=new TreeNode[arrStr.length];
		for(int i=0;i<arrStr.length;i++) {
			if(!arrStr[i].equals("null")) {
				Integer intVal=Integer.valueOf(arrStr[i]);
				TreeNode thisNode=new TreeNode(intVal);
				if(i==0) {
					root=thisNode;
				}
				treeNodeArr[i]=thisNode;
				if(i%2==0) {
					if(i/2-1>=0) {
						if(treeNodeArr[i/2-1]!=null) {
							treeNodeArr[i/2-1].right=thisNode;
						}
					}
				}else {
					if((i+1)/2-1>=0) {
						if(treeNodeArr[(i+1)/2-1]!=null) {
							treeNodeArr[(i+1)/2-1].left=thisNode;
						}
					}
				}
			}
		}
		return root;
	}
	
	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) {
			val = x;
		}
	}
}
